package com.zhz.leetcode;

import com.zhz.leetcode.entity.ListNode;
import com.zhz.leetcode.utils.LinkedListUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 234. 回文链表
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * <p>
 * 示例 1：
 * 输入：head = [1,2,2,1]
 * 输出：true
 * <p>
 * 示例 2：
 * 输入：head = [1,2]
 * 输出：false
 * <p>
 * 提示：
 * 链表中节点数目在范围[1, 105] 内
 * 0 <= Node.val <= 9
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/palindrome-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class PalindromeLinkedList234 {

    public static void main(String[] args) {
        PalindromeLinkedList234 m = new PalindromeLinkedList234();
        ListNode head = LinkedListUtils.createListNode(new int[]{1, 2, 3, 4, 3, 5, 6, 6, 4, 5, 3, 4, 3, 2, 1});
        boolean result = m.isPalindrome2(head);
        System.out.println(result);
    }

    /**
     * 思路1:先放到一个list里面去，然后使用双指针遍历list
     * 思路2:构建一个反转链表，然后一一比较
     * 这边先使用思路1实现
     */
    public boolean isPalindrome(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int left = 0, right = list.size() - 1;
        while (left <= right) {
            if (!list.get(left++).equals(list.get(right--))) {
                return false;
            }
        }
        return true;
    }

    /**
     * 使用思路2实现，利用链表反转
     */
    public boolean isPalindrome1(ListNode head) {
        //先将链表反转下  注意这边应创建一个新的链表
        ListNode tmpReversalHead = new ListNode(0);
        ListNode tmp = head;
        while (tmp != null) {
            ListNode a = new ListNode(tmp.val);
            ListNode lastNode = tmpReversalHead.next;
            tmpReversalHead.next = a;
            a.next = lastNode;
            tmp = tmp.next;
        }
        tmpReversalHead = tmpReversalHead.next;
        while (head != null) {
            if (head.val != tmpReversalHead.val) {
                return false;
            }
            head = head.next;
            tmpReversalHead = tmpReversalHead.next;
        }
        return true;
    }


    /**
     * 思路：
     * 设链表长度为len，取出len/2 之后的数据
     * <p>
     * 例如：1, 2, 3, 4, 5, 6, 3, 2, 1
     * 则取出[6, 3, 2, 1]的尾数据 和前[1, 2, 3, 4]反转[4,3,2,1]做比较，不考虑中间的节点
     * <p>
     * 难点在于如何取出倒数长度len/2 之后的数据
     * 思路：慢指针每次走一步，快指针每次走两步，这样当快指针走到尾巴的时候，慢指针走到中间
     */
    public boolean isPalindrome2(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        //算法实现第一步：
        //将链表分为两部分，奇数个的时候，最中间那个输入前半段
        ListNode slow = head, fast = head;
        ListNode pre = head, prePre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            //顺便将链表前半部分反转
            pre.next = prePre;
            prePre = pre;
        }
        if (fast != null) {
            slow = slow.next;
        }
        while (prePre != null) {
            if (prePre.val != slow.val) {
                return false;
            }
            prePre = prePre.next;
            slow = slow.next;
        }
        return true;
    }

}
